package main

import (
	"container/list"
)

type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

type LURValue struct {
	key  int
	data int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element, capacity),
		list:     list.New(),
	}
}

func (this *LRUCache) Get(key int) int {
	if elem, ok := this.cache[key]; ok {
		this.list.MoveToFront(elem)
		return elem.Value.(LURValue).data
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if elem, ok := this.cache[key]; ok {
		this.list.MoveToFront(elem)
		elem.Value = LURValue{key, value}
		this.cache[key] = elem
		return
	}

	insertRes := this.list.PushFront(LURValue{key: key, data: value})
	this.cache[key] = insertRes
	if this.list.Len() > this.capacity {
		delete(this.cache, this.list.Back().Value.(LURValue).key)
		this.list.Remove(this.list.Back())
	}
}

// 返回数组第K最大的元素
//func findKthLargest(nums []int, k int) int {
//
//}

func main() {
	//	l := &list{
	//		val: 1,
	//		next: &list{
	//			val: 2,
	//			next: &list{
	//				val: 3,
	//				next: &list{
	//					val: 4,
	//					next: &list{
	//						val: 5,
	//					},
	//				},
	//			},
	//		},
	//	}
}
